home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12870 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.2 KB
  1. Path: news.mcs.net!not-for-mail
  2. From: supercat@MCS.COM (John Payson)
  3. Newsgroups: comp.arch.embedded,comp.lang.c
  4. Subject: Re: Using malloc of C on embedded system?
  5. Date: 3 Apr 1996 02:10:05 -0600
  6. Organization: /usr/lib/news/organi[sz]ation
  7. Message-ID: <4jtbot$o1@Mars.mcs.com>
  8. References: <4jml7h$cbc@castor.usc.edu> <4jrndq$ate@kuikka.inet.fi>
  9. NNTP-Posting-Host: mars.mcs.com
  10.  
  11. In article <4jrndq$ate@kuikka.inet.fi>,
  12. Risto Jokinen  <hatrjo@hat-fi.kone.com> wrote:
  13. >This mechanism works. random size malloc/free does not work on embedded systems, or
  14. >at least it is impossible to debug, and can be VERY slow. fixed size partition pool
  15. >manager takes <<50us for malloc/free in any processor.
  16.  
  17. Fixed-size malloc/free is often a good approach if it works; to help it
  18. along, however, it's often useful to have a "version" of malloc for odd-
  19. sized blocks that will never be freed (allocate a large memory pool for
  20. these things and just track the last byte used), and sometimes useful to
  21. have several memory pools for different-sized objects.
  22.  
  23. As I mentioned in another post, the "binary buddy" system is often a good
  24. compromise between internal and external fragmentation in embedded systems.
  25. All objects consist of a power-of-two number number of "atoms" [smallest
  26. allocatable chunk] and, for simplicity, the "total" number of atoms must
  27. be a power of two [if the memory size isn't a power of two, "pre-allocate"
  28. the memory that isn't there].
  29.  
  30. If the memory size is N [N being a power of 2] atoms, the memory will then
  31. consist of N clusters of size 1, which may be paired as N/2 clusters of
  32. size 2, which may be paired as N/4 clusters of size 4, etc. up to 2 clusters
  33. of size N/2 and 1 cluster of size N.  Each cluster has a pair of bit varia-
  34. bles which indicate what size clusters could be "perfect-fit" allocated
  35. within them.
  36.  
  37. To allocate a cluster of size K, the system looks in both halves of the root
  38. cluster to see if either half has a perfect match [i.e. somewhere within
  39. that branch is a cluster of size K*2 which is already half-allocated].  If
  40. so, it checks the recurses on that branch.  If not, it checks to see if either
  41. branch has a cluster of size K*4 which is partially allocated but has space.
  42. If not, it checks for size K*8, etc.  Finally, it just checks to see if either
  43. branch has space.
  44.  
  45. Once the system has recursed to a cluster of size K*2 from which it will
  46. allocate the new block, it will then clear the "block available" bits from
  47. the parent clusters as appropriate (in particular, as it traverses up the
  48. tree, it will clear the "block available bit" for the block's size unless
  49. or until it finds a block's sibling which has that bit set.
  50.  
  51. The system is somewhat confusing to describe, but it offers lg(N) performance
  52. without too much code or--if power-of-two memory sizes work well for your
  53. application--memory overhead.  It also tends to produce minimal fragmentation:
  54. while isolated unallocated spaces may get formed when non-consecutive blocks
  55. are freed, such spaces will have effective priority when allocating new blocks.
  56.  
  57. -- 
  58. -------------------------------------------------------------------------------
  59.  supercat@mcs.com    |  "Je crois que je ne vais jamais voir...  |   J\_/L
  60.  John Payson         |   Un animal aussi beau qu'un chat."       |  ( o o )
  61.